#include<stdafx.h>
#include <time.h>
#include <stdlib.h>
#include <malloc.h>
 
int n=60;
int Visit_queue[100];
struct Pageinfo
{
int pagenum;
int breaksign;
int memorynum;
    int address;
int acess;
int modify;
};
typedef struct Lnode
{
int page;
int time;
struct Lnode *next;
}Lnode;
Lnode *l;
int empty;
Pageinfo  pagelist[60];
void Intialize()
{
int i=0;
for(i=0;i<60;i++){
pagelist[i].pagenum=i;
pagelist[i].breaksign=0;
pagelist[i].acess=0;
pagelist[i].modify=0;
}
pagelist[0].breaksign=1;
pagelist[5].breaksign=1;
pagelist[6].breaksign=1;
}
 
Lnode *CreateNode()  
{
Lnode *head;
Lnode *p;
Lnode *q;
int i;
int data[]={0,5,6,-1,-1,-1,-1,-1};
empty=8;
head=(Lnode *)malloc(sizeof(Lnode));
head->next=NULL;
p=head;
for(i=0;i<8;i++){
q=(Lnode *)malloc(sizeof(Lnode));
q->page=data[i];
if(data[i]!=-1){
q->time=1;
empty--;
}
else{
q->time =0;
}
q->next=NULL;
p->next=q;
p=q;
}
return(head);  
}
void Sequence(int k)   
{
int i;
int select;
int visit;
srand((int)time(NULL));
printf("产生的随机页面访问序列：\n\n");
for(i=0;i<100;i++){
select=rand()%4;
switch(select){
case 0:
visit=Visit_queue[i-1]+1;
if(visit<1024*60-513){
visit=visit+512;
}
break;
case 1:
visit=Visit_queue[i-1]+1;
if(visit<1024*60-513){
visit=visit+512;
}
if(visit == 61439){
visit=0;
}
break;
case 2:   
visit=rand()%(k-1);
break;
case 3:   
visit=rand()%(61439-k-1)+(k+1);
break;
}
Visit_queue[i]=visit;
printf("%3d",visit/1024);   
if((i+1)%20==0)
printf("\n");
}
}
char search(int key)
{
if(pagelist[key].breaksign==1){
return('T');
}
else{
return('F');
}
}
void FIFO(Lnode *l)
{
Lnode *p,*q,*t,*a,*h,*b;
Intialize();
    l=CreateNode();
int maxtime;
int queye=0;
int n,i,j,c;
int record=0;
printf("\nFIFO算法产生缺页中断情况：\n");
h=l->next;
a=l->next;
p=l->next;
    for(n=0;n<100;n++){
i=0;
b=l->next;
printf("\n%3d||",Visit_queue[n]/1024);
while(b!=NULL){     
printf("%3d",b->page);
b=b->next;
}
if(search(Visit_queue[n]/1024)=='F'){   
if(empty > 0){  
while(h->page!=-1){
h=h->next;
}
h->page=Visit_queue[n]/1024;
pagelist[Visit_queue[n]/1024].address=Visit_queue[n];
pagelist[Visit_queue[n]/1024].breaksign=1;
h->time=1;
empty--;
queye=queye+1;
printf("缺页中断:             ");
printf("当前物理地址:%5d 页号:%3d",pagelist[Visit_queue[n]/1024].address,Visit_queue[n]/1024);
}
else{ 
p=l->next;
maxtime=p->time;
q=p->next;
t=p;  
while(q!=NULL){
if(maxtime < q->time){
maxtime=q->time;
                        t=q;
}
q=q->next;
}
for(c=0;c<100;c++){
if(pagelist[c].pagenum == t->page){
pagelist[c].breaksign=0;
break;
}
}
printf("缺页中断:淘汰掉第%2d页 ",t->page);
t->page=Visit_queue[n]/1024;
t->time=0;
pagelist[Visit_queue[n]/1024].address=Visit_queue[n];
pagelist[Visit_queue[n]/1024].breaksign=1;
queye=queye+1;
printf("当前物理地址:%5d 页号:%3d",pagelist[Visit_queue[n]/1024].address,Visit_queue[n]/1024);
}
}
 
for(j=0;j<8-empty;j++){
a->time=a->time+1;
a=a->next;
}
h=l->next;
a=l->next;
p=l->next;
 
}
printf("\n缺页率为%2d%%\n\n",queye);
}
void LFU(Lnode *l)
 
{
    Lnode *p,*q,*t,*a,*h,*b;
Intialize();
    l=CreateNode();
int mintime;
int queye=0;
int n,i,j;
int record=0;
int th;
printf("LFU算法产生缺页中断情况：\n");
b=l->next;
h=l->next;
a=l->next;
p=l->next;
    for(n=0;n<100;n++){
i=0;
b=l->next;
printf("\n%3d||",Visit_queue[n]/1024);
while(b!=NULL){   
printf("%3d",b->page);
b=b->next;
}
if(search(Visit_queue[n]/1024)=='F'){  
if(empty > 0){
while(h->page!=-1){
h=h->next;
}
h->page=Visit_queue[n]/1024;
pagelist[Visit_queue[n]/1024].address = Visit_queue[n];
pagelist[Visit_queue[n]/1024].breaksign = 1;
pagelist[Visit_queue[n]/1024].acess = 1;  
empty--;
queye=queye+1;
printf("缺页中断:             ");
                printf("当前物理地址:%5d 页号:%3d",pagelist[Visit_queue[n]/1024].address,Visit_queue[n]/1024);
}
else{
for(j=0;j<60;j++){
if(pagelist[j].breaksign == 1){
mintime = pagelist[j].acess;
th=j;
break;
}
}
for(i=0;i<60;i++){
if(pagelist[i].breaksign==1){
if(mintime > pagelist[i].acess){
th=i;
mintime = pagelist[i].acess;
}
}
}
p=l->next;
while(p!=NULL){
if(pagelist[th].pagenum == p->page){
printf("缺页中断:淘汰掉第%2d页 ",p->page);
p->page=Visit_queue[n]/1024;  
pagelist[th].acess=0;  
pagelist[th].breaksign=0;  
break;
}
p=p->next;
}
 
pagelist[Visit_queue[n]/1024].address = Visit_queue[n];
pagelist[Visit_queue[n]/1024].breaksign = 1;
pagelist[Visit_queue[n]/1024].acess = 1;
queye=queye+1;
for(i=0;i<60;i++){   
if(pagelist[i].breaksign == 1){
pagelist[i].acess=0;
}
}
  printf("当前物理地址:%5d 页号:%3d",pagelist[Visit_queue[n]/1024].address,Visit_queue[n]/1024);
}
}
else {
pagelist[Visit_queue[n]/1024].acess++;
}
}
printf("\n缺页率为%2d%%\n\n",queye);
}
int main()
{
int k,s;
int m=8;
srand((int)time(NULL));
    k=rand()%(1024*n-1);
Sequence(k);
printf("\n选择算法:输入“1”（FIFO算法）or“2”（LFU算法）:\n");
scanf("%d",&s);
fflush(stdin);
if(s==1)
{
FIFO(l);
printf("是否计算LFU算法？\n1、是\n2、否\n");
scanf("%d",&s);
fflush(stdin);
if(s==1)
LFU(l);
else
return 0;
}
else
{
LFU(l);
printf("是否计算FIFO算法？\n1、是\n2、否\n");
scanf("%d",&s);
fflush(stdin);
if(s==1)
FIFO(l);
else
return 0;
}
return 0;
}
